繰り返し自乗法 (repeated squaring)
冪乗 $ {N^P\pmod M} を高速に計算する方法
$ {N^P} を愚直に計算するとP回の計算が必要になる
$ O(N) なのでPが大きい場合には苦しい
code:ruby
M = 10**9+7
def pow(n, power)
ans = 1
power.times do
ans *= n
ans %= M
end
ans
end
以下の3つが成り立つことを利用して高速に計算するのが繰り返し自乗法
P=偶数のとき$ {N^P = N^{P/2} * N^{P/2}}
e.g. $ {N^8 = N^4 * N^4}
P=奇数のとき$ {N^P = N * N^{P-1}}
e.g. $ {N^7 = N * N^6}
P=1のとき$ {N^P = N}
logarithmic$ O(logN) なのでPが大きくても大丈夫
code:ruby
def pow_rs(n, power)
if power == 0
1
elsif power % 2 == 0
t = pow_rs(n, power/2)
t * t % M
else
n * pow_rs(n, power-1) % M
end
end
Ocamlの例
code:ocaml
let rec pow x n =
if n = 1 then x else x * (pow x (n-1));;
let rec pow_rs x n =
if n = 1 then x
else
if n mod 2 = 0 then
let t = pow_rs x (n/2) in t * t
else
x * (pow_rs x (n-1));;
code:ruby
require 'benchmark'
Benchmark.bm(1) do |x|
x.report('pow ') { pow(2,10**8) }
x.report('pow_rs') { pow_rs(2,10**8) }
end
user system total real
pow 7.589700 0.004739 7.594439 ( 7.599576)
pow_rs 0.000011 0.000000 0.000011 ( 0.000010)
参考